#pragma once

#include "SimpleMap.h"
#include "util.h"
#include "AStarSimpleGoal.h"
#include "AStarBase.h"
#include <algorithm>
#include <list>
#include "Heap.h"
#include <boost/ptr_container/ptr_list.hpp>
#include <boost/ptr_container/ptr_vector.hpp>
using namespace std;
namespace Core
{
	namespace Util
	{
		template<class T_Goal,class T_Map,int CostScalePercent>
		class AStarMechine:public AStarBase
		{
			typedef T_Map Map;
			typedef T_Goal Goal;
			Map& mMap;
			Goal& mGoal;
			long mMaxRevolutions;
			vector<WayPoint*> mBitmap;
			boost::ptr_list<WayPoint> mCloseList;
			WayPoint* mLastNode;


			boost::ptr_list<WayPoint> mPath;
			int timeGetPath;
			bool mIsFinish;


			class Evaluator
			{
				AStarSimpleGoal& mGoal;
			public:
				Evaluator(AStarSimpleGoal& goal):mGoal(goal)
				{}
				double operator()(const WayPoint& point)
				{
					return mGoal.DistanceToGoal(point.pos);
				}
			};
			typedef WayPoint::HeapLessThen<Evaluator,CostScalePercent> LessThen;

			Evaluator evaluator;
			LessThen lessThen;
			Heap<WayPoint,LessThen> mOpenList;

		public:
			AStarMechine(Map& map,Goal& goal);
			~AStarMechine();
			virtual const boost::ptr_list<WayPoint>& GetPath(void);
			virtual void Run(void);
			virtual void SetBailoutCap(long inMaxRevolutions);
			bool IsFinish();
		};

		template<class T_Goal,class T_Map,int CostScalePercent >
		AStarMechine<T_Goal,T_Map,CostScalePercent>::AStarMechine(Map& map,Goal& goal)
			:mMap(map),mGoal(goal),mBitmap(map.GetMapSize().GetArea(),(WayPoint*)0),evaluator(mGoal),lessThen(evaluator)
			,mOpenList(lessThen), mLastNode(0),timeGetPath(0),mIsFinish(false)
		{
			Position& p=goal.GetStart();
			if(p==goal.GetDestination())
				mIsFinish=true;
			WayPoint* mockPoint=new WayPoint(Position(-1,-1),-1,0);//Add a mock point to indicate the end of the CloseList;
			mCloseList.push_back(mockPoint);


			WayPoint* wayPoint=new WayPoint(p,0,&(mCloseList.back()));
			mOpenList.push(wayPoint);
			mBitmap[p.y*mMap.GetMapSize().width+p.x]=wayPoint;
		}

		template<class T_Goal,class T_Map,int CostScalePercent>
		void AStarMechine<T_Goal,T_Map,CostScalePercent>::SetBailoutCap(long inMaxRevolutions)
		{
			mMaxRevolutions=inMaxRevolutions;
		}

		template<class T_Goal,class T_Map,int CostScalePercent>
		void AStarMechine<T_Goal,T_Map,CostScalePercent>::Run(void)
		{
			if(mIsFinish) return;
			int revolution=0;
			while(true)
			{
				WayPoint* apWayPoint=0;
				WayPoint currentWayPoint;
				if(!mOpenList.pop(apWayPoint)) 
				{
					mIsFinish=true;
					return;//use all points
				}

				currentWayPoint=*apWayPoint;

				currentWayPoint.isClosed=true;

				mCloseList.push_back(apWayPoint);

				static int dx[]={0,1,0,-1};
				static int dy[]={-1,0,1,0};
				for(int i=0;i<4;i++)
				{
					Position pos(currentWayPoint.pos.x+dx[i],currentWayPoint.pos.y+dy[i]);


					if( !mGoal.TailIsOpen(pos) ) continue;

					if( pos == currentWayPoint.parent->pos ) continue;
					double cost=currentWayPoint.cost + mGoal.GetTileCost(pos);
					int index=pos.y*mMap.GetMapSize().width+pos.x;
					WayPoint* newWayPoint=new WayPoint(pos,cost,&mCloseList.back());

					if( mBitmap[index] )//Already test
					{
						WayPoint* t=mBitmap[index];
						if(t->pos == pos && t->cost > cost && !t->isClosed)
						{
							t->cost=cost;
							t->parent=newWayPoint->parent;
						}
						continue;
					}
					mBitmap[index]=newWayPoint;
					mOpenList.push(newWayPoint);

					revolution++;
					if(pos==mGoal.GetDestination())
					{
						mLastNode=mBitmap[index];
						mIsFinish=true;
						return;
					}
					else if( revolution>mMaxRevolutions) 
					{
						mLastNode=mBitmap[index];
						return;
					}
				}
			}
		}
		template<class T_Goal,class T_Map,int CostScalePercent>
		const boost::ptr_list<WayPoint>& AStarMechine<T_Goal,T_Map,CostScalePercent>::GetPath()
		{//Get Path from the AStarMechine
		//if the search is not finished, this function will get the most likely partial pass.
			WayPoint* node=mLastNode;
			mPath.clear();
			while(node && node->pos.x>=0)
			{
				mPath.push_front(new WayPoint(node->pos,node->cost,0));
				node=node->parent;
			}
			return mPath;
		}
		template<class T_Goal,class T_Map,int CostScalePercent>
		AStarMechine<T_Goal,T_Map,CostScalePercent>::~AStarMechine(void)
		{
			mCloseList.clear();
			mPath.clear();
		}

		template<class T_Goal,class T_Map,int CostScalePercent>
		bool AStarMechine<T_Goal,T_Map,CostScalePercent>::IsFinish(void)
		{
			return mIsFinish;
		}
	}
}